'''
https://leetcode.cn/problems/linked-list-in-binary-tree/
'''


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def isSubPath(self, head, root) -> bool:
        def f(head, root):
            if head and root:
                return head.val == root.val and (f(head.next, root.left) or f(head.next, root.right))
            elif not head:
                return True
            return False

        if not root:
            return head == None
        return f(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

    def isSubPath2(self, head, root) -> bool:
        # 链表转list, 并获得kmp next 数组
        chain, table = self.to_list_and_get_kmpnext_table(head)
        n = len(chain)

        # kmp 匹配流程，可以走两个分支的比较
        def f(root, j):
            # base case, i<m and j<n
            if j == n: return True
            if not root: return False

            if root.val == chain[j]:  # i+=1, j+=1
                return f(root.left, j + 1) or f(root.right, j + 1)
            elif j != 0:  # j 还能往前跳     j = table[j]
                return f(root, table[j])
            else:  # 确实匹配不上了, i去下一位。树上就一路返回让祖先节点控制去另一条路
                # i+=1
                return f(root.left, 0) or f(root.right, 0)

        return f(root, 0)

    def to_list_and_get_kmpnext_table(self, head):
        # 链表转list
        chain = []
        cur = head
        while cur:
            chain.append(cur.val)
            cur = cur.next
        n = len(chain)
        # 生成链表的kmp next数组
        table = [-1] + [0] * (n - 1)
        i, cn = 2, 0  # [0, i), 最长（前缀和后缀，不包含[0,i)整体[ps:整体与整体必相等]）相等的长度
        while i < n:
            if chain[i - 1] == chain[cn]:
                table[i] = cn + 1
                i, cn = i + 1, cn + 1
            elif cn > 0:  # cn与i-1匹配不上，但是cn还可以继续往前跳
                cn = table[cn]
            else:  # 0与i-1都匹配不上
                table[i] = 0
                i += 1
        return chain, table

head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(8)

root = TreeNode(1)
root.left = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)

root.right = TreeNode(4)
root.right.left = TreeNode(2)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
root.right.left.right.left = TreeNode(1)
root.right.left.right.right = TreeNode(3)

print(Solution().isSubPath2(head, root))
